package org.example.linkedList;

/**
 * @Auther: wangbw
 * @Date:2020/11/19
 * @Description: org.example.linkedList
 * @version: 1.0
 */
public class LinkLoop2 {
    /**
     * 链表环相关问题:
     * 1.判断链表是否有环
     * 快慢指针，快指针走2格， 慢指针走1格。如果能相遇就是有环。
     * 2.链表的入口节点
     * 2s= 头到入口 + n圈 + 入口到相遇点； s = 头到入口 + 入口到相遇点 所以 nr = 头到入口 + 入口到相遇点 ,所以入口= nr - 入口到相遇点
     * 3.如果存在环，求环上节点的个数
     * 在2的基础上得出
     * 4.如果存在环， 求链表的长度
     * 5.求任意一个节点最远的点
     * 6.判断2个无环链表是否相交
     * 7.6基础上求2个无环链表相交点
     * @param args
     */
    public static void main(String[] args) {
        Node head = Node.createNode(8);
        Node cur = head;
        while (cur != null && cur.next != null){
            cur = cur.next;
        }
        cur.setNext(head.next.next);
        //0-1-2-3-4-5-6-7-8-2
        System.out.println(isCycle(head));
        Node node = enterNode(head);
        System.out.println(node.getData());
    }

    public static boolean isCycle(Node head) {
        Node slow = head;
        Node fast = head;
        while(fast != null && fast.next != null){

            fast = fast.getNext().getNext();
            slow = slow.getNext();
            if (fast == slow){
                return true;
            }
        }
        return false;
    }

    public static Node enterNode(Node head){
        Node slow = head;
        Node fast = head;
        Node meet = null;
        while(fast != null && fast.next != null){

            fast = fast.getNext().getNext();
            slow = slow.getNext();
            if (fast == slow){
                meet = slow;
                break;
            }
        }

        if (meet == null){
            return null;
        }

        Node start = head;
        while(start != null){
            if(start == meet){
                return start;
            }
            start = start.getNext();
            meet = meet.getNext();
        }
        return null;
    }
}
